//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 
//
// 有效括号组合需满足：左括号必须以正确的顺序闭合。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 3
//输出：["((()))","(()())","(())()","()(())","()()()"]
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：["()"]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 8 
// 
// Related Topics 字符串 动态规划 回溯 
// 👍 2078 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
var result []string
func generateParenthesis(n int) []string {
    // 回溯算法
    if n == 0 {
        return []string{}
    }

    result = make([]string, 0)

    backtrack("", n, n) // 写入初始左右括号可用数量

    return result
}

func backtrack(s string, l, r int) {
    if r == 0 {
        result = append(result, s)
        return
    }

    // 做选择
    if l > 0 {
        backtrack(s + "(", l - 1, r)
    }

    if r > l { // 右括号剩余 始终不能低于左括号
        backtrack(s + ")", l, r - 1)
    }
}
//leetcode submit region end(Prohibit modification and deletion)
